package prac10;

public class DynamicLinearProbe<K extends Hashable,D> {
	
	private Entry[] hashTable;
    private int collisions = 0;
    private int probes = 0;
    private int[] sizes = {7, 11, 23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49193};
    private int sizeControl = 0;
    private int numberOfEntries = 0;
    
    
    
    /**
	 * @return the collisions
	 */
	protected int getCollisions() {
		return collisions;
	}

	/**
	 * @return the probes
	 */
	protected int getProbes() {
		return probes;
	}

	/**
     * invariant: if an Entry is stored in position N, then
     *      N is either the hash value of the Entry's key K, or the first empty 
     *      position from the hash value when Entry was inserted. 
     * invariant (corollary of the above, really): there are
     *      no empty spaces between items with the same hash value.
     */
    private class Entry {  
        K key;
        D data;

        private Entry(K newKey, D newData) {
	    key = newKey; 
	    data = newData;
	} 

        private K getKey() {
	    return key;
	}   

        private D getData() {
	    return data;
	}

        public String toString() {
	    return key + "::"  + data;
	}
    }

    /**
     * Creates a new object of the class: empty array of the given size
     *

     * @post        an empty array of the given size
     * @complexity  best and worst case: O(1) (multiplied by the 
     *              complexity of "new")
     */
    public DynamicLinearProbe() {
    	sizeControl = 0;
    	hashTable = new DynamicLinearProbe.Entry[sizes[sizeControl+1]];
    	this.collisions = 0;
    	this.probes = 0;
    }                                                                            
    /**
     * Inserts a new element into the hash table. It returns true if the item 
     * is inserted in the first empty slot from the associated hash value, 
     * false if there are no empty slots
     *
     * @pre  the element does not already appear in the table
     * @post if it returns false, hashTable is full and left unchanged. If
     *       it returns true, hashTable has a new element, and all cells from
     *       "position" to where Entry(key,data) is finally added to, are full
     * @complexity Best case: when the first position tried is empty (i.e., 
     *       the length of the probe is 1). Then, O(1)+A where A is the 
     *       complexity of hash(), which is usually O(M) where M is the max
     *       size of the key, which is assume to be a small constant
     * @complexity Worst case: when the table is full. Then, O(TABLESIZE)+A, 
     *       since the length of the probe is equal to the size of the table.
     *       (Average is O(1) if properly constructed)
     */
    public boolean insert(K key, D data) {
		int position = key.hash(sizes[sizeControl+1], sizes[sizeControl]);
	//	System.out.println(sizeControl);
	//	System.out.println(position);
		
		if (hashTable[position] != null) {
	        collisions++;
	    }
	                                                                             
		for (int count = 0; count < hashTable.length; count++) {
		    if (hashTable[position] == null) { // empty cell
		    	hashTable[position] = new Entry(key,data);
		    	numberOfEntries++;
		    	return true;
		    } else { // still looking
		    	probes++;
			    position =(position+1)%hashTable.length;
		    	}
		}
		
		
		this.resize();
		this.insert(key, data);
			
		return false;
    }
 
    /**
     * Searches for the data associated to a particular key (if any).
     * It returns D if it can find the item, null if it cannot
     *
     * @pre none
     * @post If it returns null, there is no cell in hashTable with 
     *       the chosen key, if it returns D, then a cell with that key exists, 
     *       and has D as data. Also, hashTable is unchanged.
     * @complexity Best case: when D is in the first position (i.e., the length
     *      of the probe is 1): A+B where A is the complexity of hash(), which
     *      is usually  O(M) (where M is the max size of the elements in the 
     *      key), B is the complexity of equals() which is usually O(N) where 
     *      N is the max size of the data (note that the complexity of getKey 
     *      and getData() is O(1))
     * @complexity Worst case: when the table is full and the element is not 
            there: A+O(TABLESIZE)*B+, since the length of the probe is equal to 
     *      the size of the table. Again, average is O(1) if properly 
     *      constructed.
     */
    public D search(K key) {
	int position = key.hash();
	if (hashTable[position] != null) {
		if (!hashTable[position].getKey().equals(key)) {
            collisions++;
        }
    }
                                                    
	for (int count = 0; count < hashTable.length; count++) {
	    if (hashTable[position] == null) {
	    	return null;
	    } else if (key.equals(hashTable[position].getKey())) {
	    	return hashTable[position].getData();
	    } else {
	    	probes++;
	    	position =(position+1)%hashTable.length;
        }
    }
	return null;
    }

    /**
     * Used to print all elements in the hashTable, each in a line
     *
     * @pre none new
     * @post the hashTable is unchanged
     * @complexity Best and worst cases are the same: O(TABLESIZE)*A where 
     *      A is the complexity of the toString method for Entry 
     */
    public void printItems() {
        for (int i=0; i<hashTable.length ; i++) {
	    if (hashTable[i] != null) {
                System.out.println(hashTable[i]);
            }
        }
    }
    
    public void resize(){
    	sizeControl++;
    	if (sizeControl < sizes.length - 1) {

            Word.setPrime(sizes[sizeControl]);
            Word.setTableSize(sizes[sizeControl + 1]);

            Entry[] oldTable = hashTable;
            hashTable = new DynamicLinearProbe.Entry[Word.getTableSize()];

            for (Entry mEntry : oldTable) {
            		insert(mEntry.getKey(), mEntry.getData());
            }
        }
    }

}
